

//#include <stdio.h>
//#include <string.h>
//int main()
//{
//	char i[] = { '1','2','3',0,0};
//	printf("%d", strlen(i));
//	return 0;
//}
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* reverseList(struct ListNode* head) {
//
//    if (head == NULL)
//        return NULL;
//    struct ListNode* n1, * n2, * n3;
//    n1 = NULL;
//    n2 = head;
//    n3 = n2->next;
//
//    while (n2)
//    {
//        n2->next = n1;
//
//        n1 = n2;
//        n2 = n3;
//        if (n3)
//            n3 = n3->next;
//    }
//
//
//
//    return n1;
//}
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow, * fast;
//    slow = head;
//    fast = head;
//    while (fast->next && fast)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//
//    return slow;
//}/**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//
//
//int kthToLast(struct ListNode* head, int k) {
//    struct ListNode* slow, * fast;
//    slow = fast = head;
//
//    while (k--)
//    {
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return slow->val;
//}
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* cur1 = list1, * cur2 = list2;
//    struct ListNode* guard = NULL, * tail;
//
//    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
//    tail->next = NULL;
//
//    while (cur1 && cur2)
//    {
//        if (cur1->val < cur2->val)
//        {
//            tail->next = cur1;
//            tail = tail->next;
//            cur1 = cur1->next;
//        }
//        else
//        {
//            tail->next = cur2;
//            tail = tail->next;
//            cur2 = cur2->next;
//        }
//    }
//
//    if (cur1)
//    {
//        tail->next = cur1;
//    }
//    else
//    {
//        tail->next = cur2;
//    }
//
//    struct ListNode* head = guard->next;
//    free(guard);
//    return head;
//
//
//}
//
//
///*
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};*/
//#include <cstddef>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        struct ListNode* gGuard, * gTail, * lGuard, * lTail;
//        struct ListNode* cur = pHead;
//        gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
//        gTail->next = lTail->next = NULL;
//
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                lTail->next = cur;
//                lTail = lTail->next;
//            }
//            else
//            {
//                gTail->next = cur;
//                gTail = gTail->next;
//            }
//            cur = cur->next;
//        }
//
//        lTail->next = gGuard->next;
//        gTail->next = NULL;
//        pHead = lGuard->next;
//        free(lGuard);
//        free(gGuard);
//        return pHead;
//    }
//};



  Definition for singly-linked list.
  struct ListNode {
      int val;
      struct ListNode *next;
 };
 
  \


struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA, * curB;
    curA = headA;
    curB = headB;
    int lenA, lenB;
    while (curA)
    {
      lenA++;
        curA = curA->next;
    }
    while (curB)
    {
        lenB++;
        curB = curB->next;
    }

    if (curA != curB)
        return NULL;

    struct ListNode* LongList = headA, * ShortList = headB;

    int tmp = abs(lenA - lenB);
    if (lenA < lenB)
    {
        LongList = headB;
        ShortList = headA;
    }

    while (tmp--)
    {
        LongList = LongList->next;
    }

    while (LongList != ShortList)
    {
        LongList = LongList->next;
        ShortList = ShortList->next;
    }

    return LongList;
}








  /*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

  struct ListNode* reverseList(struct ListNode* head) {
      struct ListNode* n1, * n2, * n3;
      n1 = NULL;
      n2 = head;
      n3 = n2->next;
      while (n2)
      {
          n2->next = n1;
          n1 = n2;
          n2 = n3;
          if (n3)
              n3 = n3->next;
      }
      return n1;
  }

  struct ListNode* middleNode(struct ListNode* head) {
      struct ListNode* fast, * slow;
      fast = slow = head;
      while (fast && fast->next)
      {
          fast = fast->next->next;
          slow = slow->next;
      }
      return slow;
  }

  class PalindromeList {
  public:
      bool chkPalindrome(ListNode* A) {
          struct ListNode* mid = middleNode(A);
          struct ListNode* rhead = reverseList(mid);

          while (rhead)
          {
              if (A->val != rhead->val)
              {
                  return false;
              }
              rhead = rhead->next;
              A = A->next;
          }
          return true;
      }

  };